/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package javaapplication2;

/**
 *
 * @author Xerxes
 */
import java.io.*;
import java.lang.*;
import java.math.*;
import java.text.*;
import java.util.*;

public class uva10069 {
    BufferedReader reader;
    String s1,s2;
    int ln1,ln2;

    BigInteger [][] dp =  new BigInteger[10001][101];
    int [][] vis =  new int[10001][101];

    public static void main(String[] args)throws IOException{
        uva10069 ob = new uva10069();
        ob.run();
        System.exit(0);
    }
    public void run()throws IOException{
        reader = new BufferedReader( new InputStreamReader(System.in) );
        String line = reader.readLine().trim();
        int N = nextI(line);
        for(int i=0;i<N;++i){
            doRest();
        }
    }
    public void doRest()throws IOException{
        s1 = reader.readLine();
        s2 = reader.readLine();
        ln1 = s1.length();
        ln2 = s2.length();
        ini();
        BigInteger var = go(0,0);
        System.out.println(var);
    }
    public BigInteger go(int len1, int len2){
        if(len2==ln2){
            return BigInteger.ONE;
        }
        if(len1==ln1 && len2!=ln2){
            return BigInteger.ZERO;
        }
        if( vis[len1][len2]!=0 ){
            return dp[len1][len2];
        }
        vis[len1][len2]=1;
        BigInteger total = BigInteger.ZERO;

        if(s1.charAt(len1)==s2.charAt(len2)){
            BigInteger var1 = go(len1+1, len2+1);
            BigInteger var2 = go(len1+1, len2);
            total = total.add(var1);
            total = total.add(var2);
        }
        else{
            BigInteger var1 = go(len1+1, len2);
            total = total.add(var1);
        }
        dp[len1][len2]=total;
        return total;
    }
    public void ini(){
        for(int i=0;i<10001;++i){
            Arrays.fill( vis[i] , 0);
        }
    }
    public int nextI(String ss){
        return Integer.parseInt(ss);
    }
}
